This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present principles that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present principles. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Control flow graph (CFG) flattening is a software obfuscation technique used to make reverse engineering of a function difficult. The initial CFG of a function, made of basic blocks (BB) and jumps between them, is transformed to a functionally equivalent flattened graph. In the flattened graph, a central basic block, the dispatcher (D), leads to all other BBs, which all call back to the dispatcher. Wang first described this technique in a PhD thesis “A Security Architecture for Survivable Systems”, Department of Computer Science, University of Virginia, and in C. Wang, J. Davidson, J. Hill & J. Knight, “Protection of software-based survivability mechanisms,” In Dependable Systems and Networks 2001, DSN 2001, International Conference on. IEEE. 
FIG. 1 illustrates an exemplary function f and its corresponding CFG comprising four BBs, A-D. FIG. 2 illustrates a flattened CFG corresponding to the CFG in FIG. 1. It can be seen that the dispatcher executes a switch function S between the execution of BBs.
The control flow during execution is dependent on a dispatcher variable X. This variable is instantiated locally to a label Xi in each basic block BBi. At runtime, each basic block BBi is assigned a new label Xi+1 thereby indicating which next basic block to be executed next. A switch block then uses the dispatcher variable X to jump indirectly, via a jump table, to the intended successive basic block.
Every basic block BBi embeds instructions to compute label Xi+1 from label Xi. Caeppaert calls this a branch function [see J. Cappaert, A General Model for Hiding Control Flow, Proceedings of the tenth annual ACM workshop on DRM, ACM 2010]. In this description the branch function is denoted Bi(Xi).
As an example, in basic block A, the statement {x=i<j? 1:2} can be expressed generally as the result of a branch function BA( ): BA(XA)=BooleanFunction(inputs)*a+b. More particularly, BA(Xi)=(i<j?)*1+(i>=j?)*2. (i<j?) is a Boolean function that returns 1 or 0, so BA( ) returns 1 or 2 depending on the inputs, i and j. A branch function can be generalized to any conditional statement having more than two term conditions.
The dispatcher uses another function, the transition function F( ). In FIG. 2, this function is responsible for converting the label Xi, to an address PAi of the next BB to execute. When flattening a CFG at source code level (e.g. for a program in C language), the transition function F( ) may be implicit. For example, the switch case in the dispatcher is converted to a sequence of instructions by the compiler. However, when flattening the CFG for a low level assembly language (e.g. X86), the transition function normally has to be written expressly.
FIG. 3 illustrates a generic sequence diagram for a flattened CFG. A basic block BBi comprises two parts: a first part 30 executed upon entry to the BB and a second part 32 that is executed before leaving the BB. The second part 32 calculates the next label Xi+1 that is used by a dispatcher 34 to compute the address of the next BB and then jumps to this address. The bold border of the first part 30 indicates that this part is part of the original, non-flattened, CFG.
Basic implementations of flattened CFGs are vulnerable to static analysis attacks. By analysing each basic block and the constants used by the branch function B( ), an attacker is able to gain knowledge of dependencies between basic blocks, and then rebuild the original CFG. For example, in block 1 in FIG. 2, the conditional statement (x=i<j? 1:2) permits to deduce a relation between basic block A and basic blocks B and C.
A more generalized technique proposed by Cappaert in the previously mentioned paper consists in expressing the label Xi+1 relatively to the label Xi: Bi(Xi+1)=Xi+ai*BooleanFunction(inputs)+bi. The meaning of (ai,bi) has slightly evolved, it no longer directly expresses a label value, but relative differences between labels. However, Cappaert observes that this representation is still vulnerable to local analysis. The differences between labels restrict the set of possibilities for Xi, and thus leak information to the attacker, making brute force attacks feasible.
More specifically, the attacker has access to the code of the transition function, and thus knows the correspondence between labels Xi and addresses PAi of the basic blocks. To deduce the label of a basic block is straightforward: the attacker just has to compare the current address of the basic block and the information in the dispatcher. So for a given BBi, the attacker can guess what the current label Xi is, and then propagate the constant values (ai,bi) backward and forward to deduce the predecessor and the successor of each basic block.
It can thus be seen that the existence of a logical inference chain between embedded constants in the branch function, the logical labels, and the address of the basic block causes a problem. Existing protections find a way of breaking this chain of logical inferences.
A first solution was proposed by Wang in the previously mentioned PhD thesis. The solution focuses on the obfuscation of the embedded constants. These are not changed, but simply expressed in term of formulae, using a global array. For this purpose Wang defines a global array g_array, containing fakes values and valid values. If, for example, g_array[10]=1 and g_array[20]=1, then the constant Ci=2 can be expressed by mathematical operation on elements of the array: Ci=(g_array[10]+g_array[20]) mod N. However, the solution is hardly more robust as the array is static and constant. By obtaining access to the array through reverse engineering, an attacker can resolve the different formulae.
To counter this attack, Wang further proposes to periodically reshuffle and redistribute the content of g_array using a redistribution function that is invoked outside of the flattened function. Ideally, this solution could be secure if the redistribution is not done externally, but internally in the flattened function during transition between basic blocks. However, Wang does not give any clues on how to achieve this. Moreover, there is a further difficulty. In a graph, multiple paths can lead to the same basic block. If for example both basic blocks A and B lead to C, then the content of the array is not deterministic in C.
A second solution was proposed by Jung Ge et al. [See Jung Ge, Soma Chaudhuri, Akhilesh Tyagi: Control Flow Based Obfuscation, in Proceedings of DRM 05, the 5th ACM Workshop on Digital Rights Management]. According to this solution called CFI-hiding scheme, based upon Aucsmith's algorithm, sets of basic blocks are shuffled, XORed together, and dynamically deciphered at execution by a monitoring process called Self-modifying scheme. At any time the only set of basic block that is in clear text is the one that is already executed. [See D. Aucsmith: Tamper Resistant Software: An Implementation, in R. J. Anderson, editor, Information Hiding, volume 1174 of Lecture Notes in Computer Science].
A third solution was provided by Apple in patent application US 2013/0232323 that describes a solution that obfuscates the control flow in a different way. All calls are replaced by indirect jumps using a jump table. The basic blocks are not encrypted, but the jump table is; only a portion of the jump table is in the clear at a given time.
A common drawback with self-modifying schemes like the one by Jung Ge et al. is that the program requires write permission on itself. Such protection techniques are sometimes not allowed on some application platforms, like the iOS appstore, for which these techniques are assimilated to polymorphic viruses. Thus a protected application would not pass the security verifiers in charge of verifying the safety of the application before publishing it. Another problem with self-modifying techniques is their vulnerability to replay attacks. The randomization induced by the protection can be overcome if the attacker has means to restart execution from a backup initial state.
A fourth solution was provided by Cappaert in the previously mentioned paper. The solution uses a one-way function, typically a hash function applied on label values Xi when entering the dispatcher. The resulting value is then matched against a series of if . . . then clauses to determine the next address.
By static analysis of the dispatcher in depth, an attacker obtains knowledge of all the possible images of label values by the hash function and of all addresses referenced. But as the hash function is not invertible, the antecedent label values cannot be obtained with certainty. By coding the label values with enough bits (for example a 128-bit random number), the input domain of the hash function cannot be enumerated by brute force. The attacker then cannot predict which antecedent Xi label values leads to a given Zi value, and, thus, the corresponding antecedent address values.
It will be appreciated that this stops logical backward inference and makes forward inference more complex. In other words, the attacker cannot statically predict the predecessor of a basic block, and the constants used in the branching function have only a meaning for logical labels, and do not express indirectly constraints to basic block addresses. Hence, differences values between labels are no longer exploitable.
Unfortunately, while this solution provides good security, it has a serious drawback in terms of performance. The drawback stems from the dispatcher. In practice, the compiler replaces the dispatcher's switch statement by a cascade of if . . . else condition statements. Given a CFG that has N basic blocks, the switch case will result in the cascade of N more conditional statements, so N more conditional basic blocks. A first consequence is that the number of total basic blocks in the CFG is multiplied by two (twice more times jump instructions). A second consequence is that each time the processor executes the dispatcher, it faces a cascade of N conditional statements, which results in the cost of potentially 2*N additional instructions. Moreover, this technique adds many comparisons and jump instructions to the execution, and also stresses the branch prediction much. For each missed branch prediction the processor started to execute instructions that then are not executed and the processor then has to ‘undo’ everything before continuing execution at the right address.
Indeed, when using a flattened CFG based upon switch case, execution time is proportional to the square of the number of basic blocks (O(n2)). The time penalty is so great for large functions that it is difficult to envisage the solution to protect a major part of the protected binary. As a result, to keep a good execution performance, the coverage of the protection has to be limited to only some sensitive portions of the code, which naturally decreases the security. The poor performance result is a direct consequence of the selected hash function; the outputs of such functions are discontinuous values that cannot be mapped directly to an indexed table.
It will thus be appreciated that there is a need for a CFG flattening solution addresses these and other problems. The present principles can provide such a solution.